# 给定一个非负整数数组，你最初位于数组的第一个位置。
# 数组中的每个元素代表你在该位置可以跳跃的最大长度。
# 你的目标是使用最少的跳跃次数到达数组的最后一个位置。


class Solution:
    def jump(self, nums):
        len_num, res = len(nums), 0
        i = len_num - 1
        while i > 0:
            for j in range(0, i):
                if j + nums[j] >= i:
                    i = j
                    res += 1
                    break
        return res

    def jump2(self, nums):
        road_dic, len_num = {}, len(nums)
        for index, num in enumerate(nums):
            if num + index < len_num-1:
                h = num + index
                while h >= index+1:
                    if h not in road_dic:
                        road_dic[h] = index
                    else:
                        break
                    h -= 1
            else:
                road_dic[len_num-1] = index
                break
        print(road_dic)
        i, res = len(nums) - 1, 0
        while i > 0:
            i = road_dic[i]
            res += 1
        return res


a = Solution()
print(a.jump2([5,9,3,2,1,0,2,3,3,1,0,0]))
